The present invention relates to a method and apparatus for recommending television programming, and more particularly, to a method and apparatus for recommending television programming through the use of decision trees.
As the number of channels available to television viewers has increased, along with the diversity of the programming content available on such channels, it has become increasingly challenging for television viewers to identify television programs of interest. Historically, television viewers identified television programs of interest by analyzing printed television program guides. Typically, such printed television program guides contained grids listing the available television programs by time and date, channel and title. As the number of television programs has increased, the ability to effectively identify desirable television programs using such printed guides has become impractical.
More recently, television program guides have become available in an electronic format, often referred to as electronic program guides (EPGs). Like printed television program guides, EPGs contain grids listing the available television programs by time and date, channel and title. An EPG, however, allows television viewers to sort or search the available television programs in accordance with personalized preferences. In addition, EPGs allow for on-screen presentation of the available television programs.
While EPGs allow viewers to identify desirable programs more efficiently than conventional printed guides, they suffer from a number of limitations, which if overcome, could further enhance the ability of viewers to identify desirable programs. For example, many viewers have a particular preference towards, or bias against, certain categories of programming, such as action-based programs or sports programming. Thus, the viewer preferences can be applied to the EPG to obtain a set of recommended programs that may be of interest to a particular viewer.
Thus, a number of tools have been proposed or suggested for recommending television programming. The Tivo (trademark) system, for example, commercially available from Tivo, Inc., of Sunnyvale, Calif., allows viewers to rate shows using a xe2x80x9cThumbs Up and Thumbs Downxe2x80x9d feature and thereby indicate programs that the viewer likes and dislikes, respectively. Thereafter, the TiVo receiver matches the recorded viewer preferences with received program data, such as an EPG, to make recommendations tailored to each viewer.
Thus, such tools for recommending television programming provide selections of programs that a viewer might like, based on the viewer""s past viewing history as well as a profile containing viewer preferences. In fact, such tools for recommending television programming generally require explicit profile information from the user. Viewers, however, may not take the time required to sufficiently detail their viewing preferences in a user profile. A need therefore exists for a method and apparatus for recommending television programming based on the viewer""s past viewing history. A further need exists for a method and apparatus for recommending television programming that does not require any explicit profile information from the viewer.
Generally, a method and apparatus are disclosed for recommending television programming using decision trees. According to one aspect of the invention, inductive principles are utilized to identify a set of recommended programs that may be of interest to a particular viewer, based on the past viewing history of a user.
The present invention monitors a user""s viewing history and analyzes the shows that are actually watched by a user (positive examples) and the shows that are not watched by the user (negative examples). For each positive and negative program example (i.e., programs watched and not watched), a number of program attributes are classified in the user profile, such as the time, date, duration, channel, rating, title and genre of a given program. The various attributes are then positioned in the hierarchical decision tree based on a ranking of the entropy of each attribute. Each node and sub-node in the decision tree corresponds to a given attribute from the user profile. Each leaf node in the decision tree corresponds to either a positive or negative recommendation for a program mounted at the corresponding leaf node. The decision tree attempts to cover as many positive examples as possible but none of the negative examples.
The television programming recommender of the present invention processes a user profile, if available, and the viewing history of a user to generate a decision tree. The decision tree is built using a decision tree process that implements a xe2x80x9ctop-down divide and conquerxe2x80x9d approach. The decision tree can thereafter be applied to an electronic program guide to make program recommendations. The program recommendations may be, for example, a set of recommended programs that may be of interest to a particular viewer.